nums = [4,0,5,-5,3,3,0,-4,-5]
target = -2

import time
time_1 = time.time()

nums.sort()
lenth = len(nums)
min_diff = 10000000
ans = -target
for i in range(lenth-2):
    if nums[i] + nums[-2] + nums[-1] - target <= 0:
        if abs((nums[i] + nums[-2] + nums[-1])-target) < min_diff:
            min_diff = abs((nums[i] + nums[-2] + nums[-1])-target)
            ans = nums[i] + nums[-2] + nums[-1]
        continue
    elif nums[i] + nums[i+1] + nums[i+2] - target >= 0:
        if abs((nums[i] + nums[i+1] + nums[i+2])-target) < min_diff:
            min_diff = abs((nums[i] + nums[i+1] + nums[i+2])-target)
            ans = nums[i] + nums[i+1] + nums[i+2]
        continue

    j = i+1
    k = lenth-1
    diff_buf = abs(nums[i] + nums[j] + nums[k] - target)
    while j!=k:
        diff = abs(nums[i] + nums[j] + nums[k] - target)
        if diff > diff_buf:
            break

        if diff < min_diff:
            min_diff = diff
            ans = nums[i] + nums[j] + nums[k]
        
        if nums[i] + nums[j] + nums[k] <= target:
            j += 1
        elif nums[i] + nums[j] + nums[k] > target:
            k -= 1

        diff_buf = diff

print(ans,time.time()-time_1)